/*
Source : https://leetcode.com/problems/add-binary/
Author : nflush@outlook.com
Date   : 2016-07-18
*/

/*
67. Add Binary
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 93227
?Total Submissions: 328384
?Difficulty: Easy



Given two binary strings, return their sum (also a binary string). 

For example,
 a = "11"
 b = "1"
 Return "100". 



Subscribe to see which companies asked this question
*/
class Solution
{
public:
    string addBinary(string a, string b)
    {
        if(a.size() < b.size()) return addBinary(b, a);
        string ret = a;
        int    lena = a.size();
        int    lenb = b.size();
        int    up = 0;

        while(lenb > 0) {
            lena--;
            lenb--;
            if(ret[lena] == '1' && b[lenb] == '1') {
                if(!up) {
                    up = 1;
                    ret[lena] = '0';
                }
            } else if(ret[lena] == '1' || b[lenb] == '1') {
                if(up) {
                    ret[lena] = '0';
                } else {
                    ret[lena] = '1';
                }
            } else {
                if(up) {
                    ret[lena] = '1';
                    up = 0;
                }
            }
        }
        while(up && lena > 0) {
            lena--;
            if(ret[lena] == '1') {
                ret[lena] = '0';
            } else {
                ret[lena] = '1';
                up = 0;
            }
        }
        if(up) return string("1") + ret;
        return ret;
    }
};

/* 180226 */
/* 294 / 294
    time�F4 ms */
class Solution
{
public:
    string addBinary(string a, string b)
    {
        if(a.size() < b.size()) return addBinary(b, a);
        string ret = a;
        int    lena = a.size();
        int    lenb = b.size();
        char   up = '0';

        while(lenb > 0) {
            lena--;
            lenb--;
            if(b[lenb] == up) {
                /* carry is same with b,('0' or '1'),ret is no need change */
                ;
            } else {
                /* differ,change carry and the ret */
                up = ret[lena];
                ret[lena] = '1' - ret[lena] + '0';
            }
        }
        while(up != '0' && lena > 0) {
            lena--;
            if(ret[lena] == '1') {
                ret[lena] = '0';
            } else {
                ret[lena] = '1';
                up = '0';
                return ret;
            }
        }
        if(up != '0') return string("1") + ret;
        return ret;
    }
};


class Solution
{
public:
    string addBinary(string a, string b)
    {
        if(a.size() < b.size()) return addBinary(b, a);
        string ret = a;
        int    lena = a.size();
        int    lenb = b.size();
        char   up = '0';

        while(lenb > 0) {
            lena--;
            lenb--;
            if(b[lenb] == up) {
                ;
            } else {
                up = ret[lena];
                ret[lena] = '1' - ret[lena] + '0';
            }
        }
        if(up != '0') {
            while(lena > 0) {
                lena--;
                if(ret[lena] == '1') {
                    ret[lena] = '0';
                } else {
                    ret[lena] = '1';
                    return ret;
                }
            }
            return string("1") + ret;
        }
        return ret;
    }
};